#include<iostream>

using namespace std;

typedef long long ll;

int p;

int qmi(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(ll)res*a%p;
        b>>=1;
        a=(ll)a*a%p;
    }
    return res;
}

int C(int a,int b)
{
    int res=1;
    for(int i=1,j=a;i<=b;++i,--j)
    {
        res=(ll)res*j%p;
        res=(ll)res*qmi(i,p-2)%p;
    }
    return res;
}

int lucas(ll a,ll b)
{
    if(a<p&&b<p) return C(a,b);
    return (ll)C(a%p,b%p)*lucas(a/p,b/p)%p;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ll a,b;scanf("%lld%lld%lld",&a,&b,&p);
        cout<<lucas(a,b)<<endl;
    }
    return 0;
}